package com.fw.leetcode.doublepointer;

import com.fw.leetcode.LeetCode;

/**
 * 26. Remove Duplicates from Sorted Array
 *
 * Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place
 * such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
 *
 * Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
 * ·Change the array nums such that the first k elements of nums contain the unique elements in the order
 *      they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
 * ·Return k.
 *
 * Custom Judge:
 * The judge will test your solution with the following code:
 *  | int[] nums = [...]; // Input array
 *  | int[] expectedNums = [...]; // The expected answer with correct length
 *  |
 *  | int k = removeDuplicates(nums); // Calls your implementation
 *  |
 *  | assert k == expectedNums.length;
 *  | for (int i = 0; i < k; i++) {
 *  |     assert nums[i] == expectedNums[i];
 *  | }
 * If all assertions pass, then your solution will be accepted.
 *
 * Example 1:
 *  Input: nums = [1,1,2]
 *  Output: 2, nums = [1,2,_]
 *  Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
 *               It does not matter what you leave beyond the returned k (hence they are underscores).
 *
 * Example 2:
 *  Input: nums = [0,0,1,1,1,2,2,3,3,4]
 *  Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
 *  Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
 *               It does not matter what you leave beyond the returned k (hence they are underscores).
 *
 * Constraints:
 *  1 <= nums.length <= 3 * 10^4
 *  -100 <= nums[i] <= 100
 *  nums is sorted in non-decreasing order.
 */
public class Num_0026 implements LeetCode {
    private interface Solution {
        int removeDuplicates(int[] nums);

        default void assertEquals(int[] nums, int[] expected) {
            int[] oldNums = new int[nums.length];
            System.arraycopy(nums, 0, oldNums, 0, nums.length);
            int k = removeDuplicates(nums);
            if (k != expected.length) {
                removeDuplicates(oldNums);
                return;
            }
            for (int i = 0; i < k; i++) {
                if (nums[i] != expected[i]) {
                    removeDuplicates(oldNums);
                    return;
                }
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int removeDuplicates(int[] nums) { // 双指针：时O(n) 空O(1)
            /*
             * 删除有序数组中的重复项（原位操作）
             */
            if (nums.length == 0) return 0;
            if (nums.length == 1) return 1;
            int idx1 = 0;
            int idx2 = 1;
            while (idx1 < nums.length && idx2 < nums.length) {
                if (nums[idx1] != nums[idx2]) {
                    if (idx2 - idx1 > 1) { // 存在间距，向前移
                        nums[idx1 + 1] = nums[idx2];
                    }
                    idx1++;
                }
                idx2++;
            }
            return idx1 + 1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertEquals(new int[]{}, new int[]{});
        solution.assertEquals(new int[]{1}, new int[]{1});
        solution.assertEquals(new int[]{1,2}, new int[]{1,2});
        solution.assertEquals(new int[]{1,1,2}, new int[]{1,2});
        solution.assertEquals(new int[]{0,0,1,1,1,2,2,3,3,4}, new int[]{0,1,2,3,4});
    }
}
